This invention relates to cryptographic communications methods and systems that use a public key protocol, and more particularly to verifying the cryptographic security of a selected public and private key pair without knowing the private key.
Cryptographic systems are adapted to transfer securely messages between remote locations over unsecured communication networks. Such systems include at least one encoding device at a first location and at least one decoding device at a second location, with the encoding and decoding devices all being coupled to the network. The encoding device accepts, as inputs, a message-to-be-encoded (M) and an encoding key or encryption operator (E). The encoding device transforms the message M in accordance with the encryption operator to produce an encoded version (C) of the message (which is denoted as the ciphertext), where C=E(M). The decoding device accepts, as inputs, a ciphertext-to-be-decoded C and a decoding key or operator (D). The decoding device transforms the ciphertext in accordance with the decryption operator to produce a decoded version (Mxe2x80x2) of the ciphertext, wherein Mxe2x80x2=D(C) or Mxe2x80x2=D(E(M)) and Mxe2x80x2=M for all messages. Like the encoding key, the decoding key and decoded message Mxe2x80x2 are digital sequences.
In a public-key cryptosystem, each user (e.g., user A) publishes an enciphering operator, or a public key, EA. User A keeps private the details of the corresponding deciphering private key DA which satisfies the equation DA (EA (M)=M for any message M. In order for the public key system to be practical, both EA and DA must be efficiently computable. Furthermore, user A must not compromise the cryptographic security of DA when revealing EA. That is, it should not be computationally feasible for an eavesdropper to find an efficient way of computing DA given only a specification of the enciphering key EA. In a public key system, a cryptographically secure selection of keys ensures that only user A is able to compute DA efficiently. Whenever another user (e.g., user B) wishes to send a message M to A, that user encodes M using the publicly-available EA and then sends the enciphered message EA(M) to user A. User A deciphers the message by computing (DA(EA(M))=M. Since DA is not derivable from EA in a practical way, only user A can decipher the message EA(M). If user A wants to send a response to user B, user A enciphers the message using user B""s encryption key EB, also available in publicly.
The public key approach is also used to provide signed digital messages that are both message-dependent and signer-dependent. The recipient of a xe2x80x9csignedxe2x80x9d message not only knows the message substance, but is also assured that the message originated from the identified sender. A signed message precludes the possibility that a recipient could modify the received message by changing a few characters or that the recipient could attach the received signature to any message whatsoever.
When user A wants to send user B a xe2x80x9csignedxe2x80x9d document M, user A first uses his own decryption key DA to transform M into a signed message word Ms, where MS=DA(M). User A then uses user B""s publicly-available encryption key EB to generate a signed ciphertext word CS=EB(MS)=EB(DA(M)), which is sent to user B. User B initially uses his secret decryption key DB to reduce the signed ciphertext CS to a signed message word in accordance with DB(CS)=DB(EB(MS))=MS. Now using user A""s publicly-available encoding key EA, user B decodes the signed message word in accordance With EA(MS)=EA=M. User A cannot deny having sent user B this message, since no one but A could have created MS=DA(M), provided that DA is not Computable from EA, i.e. provided that DA is cryptographically secure. Furthermore, user B can show that the public key EA is necessary to extract the message M so that user B has xe2x80x9cproofxe2x80x9d that user A has signed the document. User B cannot modify M to a different version Mxe2x80x2, since then user B would have to create the corresponding signature DA(Mxe2x80x2) as well. Therefore user B must have received a document xe2x80x9csignedxe2x80x9d by A, which he can xe2x80x9cprovexe2x80x9d that A sent, but which B cannot modify in any detail.
In a communication system which is adapted to pro)vide digital signatures, each transmitting and receiving terminal is provided with both an encoding and decoding device, each device being functionally equivalent to the devices described above but operating on a different set of input words with a different key. The transmitting terminal decoding device transforms a message M using its own decoding key to generate a signed message MS. Then the encoding device transforms the resultant signed message MS with the intended receiving terminal""s encoding key to generate signed ciphertext word CS. The receiving terminal""s decoding device then transforms the received CS with its own decoding key to obtain the signed message MS, and then the encoding device transforms the resultant signed message with the transmitting terminal""s encoding key to obtain the original message. For example, in a system for transmitting signed messages from user A to user B, the terminal for user A includes at least one encoding device characterized by an encoding key EB=(eB, NB) and at least one decoding device, characterized by a decoding key DA=(dA, NA). Similarly, the terminal for user B includes an encoding device characterized by an encoding key EA=(eA, NA) and a decoding device characterized by a decoding key DB=(dB, NB). The encoding and decoding devices of terminals A and B are described above.
In operation, to provide a signed message, user A first generates a ciphertext signed message word MS
Msxe2x89xa1MdA(mod NA)
and then transforms that signed message word to a signed ciphertext word CS: which is then transferred to user B. User A may readily use DA and NA from his own
xe2x80x83CS=MSeB(mod NB)
decoding key to reduce the signed ciphertext word to a signed message word, and then perform the encoding transformations using EB and NB from the publicly available file.
User B deciphers the received CS into the signed message word MS in accordance with
MSxe2x89xa1(CS)dB(mod NB)
User B then transforms MS to M in accordance with
Mxe2x89xa1MSeA(mod NA)
User B may readily perform his decoding transformations since DB and NB are part of his decoding key and EA and NA are readily available on the public file.
Because public key cryptography can be used for authentication of transactions, a cryptographically strong key pair (i.e. a public key and a corresponding private key) is desirable to prevent a party to a transaction from subsequently repudiating it. If a transaction is authenticated with a weak key pair, it is easier for a party to the transaction to subsequently repudiate it by arguing that the private key had succumbed to a cryptanalytic attack.
When business transactions are conducted over an unsecured network there is a critical need to assure the cryptographic security of the private key. The integrity of the transactions are assured not only by preventing an unauthorized party to decipher or alter the transmitted message, or by uniquely identifying the sender, but also by preventing the sender from repudiating the transaction later. That is, the author should be the constructor of the private key and the only party having access to the private key. On the other hand, a certifying authority (i.e., a verifier) should be able to verify the cryptographic security of the private key without receiving information sufficient to calculate the private key. In a certifying process, the constructor (i.e., the prover) would prove the cryptographic security of the selected private key to the verifier while interacting over the unsecured network. Certification authorities validate key pairs. This validation usually involves the assumption of liability. It is desirable for a certification authority to verify the cryptographic security of a key pair before validating it and thus assuming liability on its behalf.
The best known factoring algorithms which can be used for cryptanalytic attacks are the Elliptic Curve Method (ECM), the Quadratic Sieve (QS), and the Number Field Sieve (NFS). The computational run-time required by the Number Field Sieve does not depend on the size of the factors. The Number Field Sieve is described in Lenstra, A. K., and Lenstra, Jr., H. W., eds., Lecture Notes in Mathematics 1554: The Development of the Number Field Sieve, Springer-Verlag, 1993. The run-time necessary for ECM to find a factor p of a larger integer N depends on the size of p. Finding factors greater than 60 decimal digits is regarded as impractical with current computer technology. To make the factoring of N as difficult as possible means making p too large for ECM. This is accomplished by taking p to be just slightly smaller than {square root over (N)}.
Two other cryptanalytic attacks known in the art are the Pollard Pxe2x88x921 factoring algorithm and the Williams P+1 factoring algorithm. These algorithms can succeed in factoring N=pq if either pxc2x11 or qxc2x11 has only small prime factors. To make the factoring of N as difficult as possible means selecting p and q such that pxe2x88x921, p+1, qxe2x88x921, and q+1 all have large prime factors.
Another cryptanalytic attack is described in E. Bach and J. Shallit, Factoring with Cyclotomic Polynomials, Math. Comp. 52 (1989), 201-219. The Bach-Shallit algorithm can succeed in factoring N=pq if cyclotomic polynomials in either p or q have only small prime factors. To make the factoring of N as difficult as possible means selecting p and q such that cyclotomic polynomials in p and q all have large prime factors.
Another cryptanalytic attack is the weighted difference of squares algorithm. This algorithm can succeed in factoring N=pq if p and q are too close together, which allows N to be represented as x2-y2. To make the factoring of N as difficult as possible means selecting p and q such that the ratio p/q is not approximated by a ratio a/b, where a and b are two reasonably small integers.
As can be seen from above, the underlying cryptographic security of the public key cryptographic protocols rests upon the difficulty of factoring large composite integers. The systems and methods described herein enable an entity to prove to a verifying entity that the constructed private key is cryptographically secure without revealing sufficient information to factor the private key.
In one aspect, this invention provides methods and systems for demonstrating that a number N is the product of two large prime factors without revealing any information about its factors.
In another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to Pollard Pxe2x88x921 factoring attacks without revealing any information about its factors. In yet another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to Williams P+1 factoring attacks without revealing any information about its factors.
In another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to Bach-Shallit cyclotomic polynomial factoring attacks without revealing any information about its factors.
In another aspect, this invention provides methods and systems for demonstrating that a number N is resistant to weighted difference of squares factoring attacks without revealing any information about its factors.